\chapter{Running Example}

%HUSSAIN
%HUSSAIN

%HUSSAIN PUT THE RUNNING EXAMPLE HERE (IF NEEDED USE AND MODIFY THE CONTENT BELOW, (THE CONTENT BELOW IS MINE, I STARTED WRITING THE RUNNING EXAMPLE))

Following the pattern presented by Kundu et al \cite{kundustructural} in our considered technical report, we have chosen XML for our running example. XML data can be represented as a tree structure. Due to the widespread use of XML in web services, content management, databases etc, its integrity and confidentiality becomes important.
\newline

\begin{figure}[!h]
	\centering
	\includegraphics[scale=0.7]{Images/Travel_Record.png}
	\caption{Tree representation of the TravelRecord.}
	%\label{}
	%\cite{}
\end{figure}

\lstinputlisting[language=Xml,float=h,tabsize=2,frame=single,caption=XML representation of Travel Record schema,captionpos=b]{Images/Travel_Record.xml}
In the Example we are considering $\mathit{TravelRecord}$ of a person, which indeed contains some sensitive information. This type of schema can be used for some travel agency database or some tourist management system. In our XML based tree record, the root node $\mathit{TravelRecord}$ contains two subtrees having customer information and journey information. Customer information starts with $\mathit{CustomerID}$. Under each $\mathit{CustomerID}$ node, the database contains personal credentials like $\mathit{Name}$, $\mathit{Contact}$,  $\mathit{Age}$ and $\mathit{Membership Type}$ of the passenger. Many travel companies offer membership benefits by tendering three kinds of memberships i.e. temporary, permanent and executive members which is stored in the node \\$\mathit{Membership Type}$. Offers are often shortlisted on the basis of membership status.  Under the $\mathit{Contact}$ node, there are two modes of contact i.e. via $\mathit{Email}$ and via $\mathit{Phone}$. Second subtree comprises of $\mathit{Journey Info}$. Under journey information we have $\mathit{Location}$ of the current voyage, there can be multiple locations for each passenger as a person is capable of undertaking more than one journey. These different journeys can be identified uniquely (say we can have a composite key made of $\mathit{City}$, $\mathit{Location}$ and $\mathit{Date}$). Each journey is composed up of $\mathit{Date}$, name of the $\mathit{Hotel}$, destination $\mathit{City}$ and $\mathit{reason}$ for travel. Reason is not a mandatory information but is mostly intrigued due to security reasons. Most travel agencies also offer accommodation and thus we can store the accommodation details as $\mathit{Number of Days}$ and $\mathit{Room Type}$. Room type can be normal or executive as per customer’s requirement.
\newline

Merkle Hash Technique is used to sign the record and hence the data is authenticated by bottom up concatenating of hashes. As we have discussed that MHT is not an accomplished authentication scheme so a lot of information is exposed by leakage. Figure 5.1 shows two subtrees which are shared under different scenarios. 
\newline

For example to calculate the Merkle hash of $\mathit{ContactID}$ D$_{4:0}$, hashes of $\mathit{Name}$, $\mathit{Contact}$, $\mathit{Age}$ and $\mathit{Membership Type}$ will be required. When a subtree T$_{\delta1}$ is shared it will expose the hash of $\mathit{Phone}$ of the customer and that it is the left sibling of $\mathit{Email}$. It leaks the hashes $\mathit{Name}$, $\mathit{Age}$ and $\mathit{Membership Type}$ and the fact that they are siblings. It also reveals that $\mathit{Name}$ is to the left of $\mathit{Contact}$, and $\mathit{Age}$ and $\mathit{Membership Type}$ are to the right of $\mathit{ContactID}$. These leakage can lead to an inference attacks.
\newline

To calculate the hash of $\mathit{Location}$ D$_{3:5}$, we require hashes of $\mathit{Date}$, $\mathit{Hotel}$, $\mathit{City}$ and $\mathit{Reason}$. These details when shared can lead to catastrophic consequences. It will reveal that a certain person is in some city on certain date due to certain reason, which beaches a person's privacy.
\newline

Suppose a scenario in which a person who is in-charge of promotion of some offers needs access to $\mathit{ContactID}$ and contact information via $\mathit{Email}$ (requests subtree T$_{\delta1}$). In order to authenticate this information, he is provided with the auxiliary information. Using this auxiliary information he can deduce that there is another sibling of $\mathit{Email}$. He can easily conclude that it is $\mathit{Phone}$ (it is very common that phone and email are kept under contact information). If the ordering of the siblings have any meaning (like preferred mode of contact of the customer) then it also gets leaked. He can also infer that there are other personal information available for a certain customer under $\mathit{CustomerID}$ (also the count of nodes stored under this node) because their hashes are required to authenticate $\mathit{CustomerID}$. Suppose the database does not store the edge to $\mathit{Member Type}$ if the customer is not a member, then in that case by knowing the count of nodes one can infer if a customer is a member or not.
\newline 

We can consider another scenario based upon the discussed schema. Suppose that this travel agency manages visa issues as well. Suppose subtree T$_{\delta2}$ is shared to an immigration officer for credentials of customers regarding which $\mathit{City}$ of the $\mathit{Country}$ will be visited by customer. He will authenticate this information by utilizing the Merkle hashes of $\mathit{Hotel}$, $\mathit{Reason}$ and $\mathit{Date}$. This leakage poses vivid inference about the customer’s accommodation. Immigration officer can presume that the siblings contain information regarding his stay details. He can leak this info to competitor hotels and also to other travel agencies which are on the panel of that immigration office. Further, he can infer about other journeys of the customer, the number of journeys and their temporal order(if sibling order of $\mathit{JourneyInfo}$ is related to time).


